package DataStructureBook.testMaxSubSum;

/**
 * 求最大子序列和
 */
public class Test2 {
    public static void main(String[] args) {
        int[] arr = {-2, 11, -4, 13, -5, -2};
        int res1 = maxSubSum1(arr);
        int res2 = maxSubSum2(arr);
        int res3 = maxSubSum3(arr);
        System.out.println("maxSubSum1: "+res1);
        System.out.println("maxSubSum2: "+res2);
        System.out.println("maxSubSum3: "+res3);
    }

    public static int maxSubSum1(int[] arr) {
        int maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int thisSum = 0;
                for (int k = i; k <= j; k++) {
                    thisSum += arr[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    public static int maxSubSum2(int[] arr) {
        int maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            int thisSum = 0;
            for(int j = i; j < arr.length; j++){
                thisSum += arr[j];
                if(thisSum > maxSum){
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    public static int maxSubSum3(int[] arr){
        int maxSum = 0,thisSum = 0;
        for(int j = 0;j < arr.length; j ++){
            thisSum += arr[j];
            if(thisSum > maxSum){
                maxSum = thisSum;
            }else if(thisSum < 0){
                thisSum = 0;
            }
        }
        return maxSum;
    }

    //幂运算
    public static long pow(long x,int n){
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return x;
        }
        if(isEven(x)){
            return pow(x*x,n/2);
        }else {
            return pow(x*x,n/2)*x;
        }
    }

    public static boolean isEven(long x){
        if(x % 2 == 0){
            return true;
        }
        return false;
    }

    
}
